W10. Relations and Graphs

1. Theory

1.1 Introduction to Relations

A relation is a fundamental concept in mathematics that describes how elements from different sets are connected or associated with each other. Formally, any subset of a Cartesian product of sets is called a relation. If we have sets , then any set is a relation on these sets.

Relations can have different arities (number of elements involved). A unary relation (arity 1) describes a property of individual elements, like “x is positive” or “a person is a woman.” A binary relation (arity 2) connects pairs of elements, such as “x is less than y” or “person x is married to person y.” Higher-arity relations involve three or more elements, like “x + y = z” connecting three numbers.

1.1.1 Binary Relations

A binary relation on sets and is any subset . When , we say is a binary relation on (rather than “between” two different sets). We write or equivalently to indicate that elements and are related.

For example, the relation “less than or equal to” on natural numbers is the set . This is an infinite set containing pairs like .

1.2 Properties of Binary Relations

Binary relations can have various important properties that characterize their behavior. Understanding these properties is crucial for classifying relations and studying their applications.

1.2.1 Reflexivity and Irreflexivity

A relation on set is reflexive if every element is related to itself: . For example, “equals” (=) is reflexive because for all . The relation “is less than or equal to” () is also reflexive.

Conversely, a relation is irreflexive (also called anti-reflexive) if no element is related to itself: . The relation “less than” (<) is irreflexive because is never true.

Important: A relation can be neither reflexive nor irreflexive. For instance, “person x likes person y” may hold for some people with themselves but not others.

1.2.2 Symmetry, Asymmetry, and Anti-symmetry

A relation on set is symmetric if whenever is related to , then is also related to : . Examples include “equals” (if then ) and “x + y = 0” (if then ).

A relation is asymmetric if whenever is related to , then is NOT related to : . This is equivalent to saying — you can never have both and simultaneously. The relation “less than” (<) is asymmetric.

A relation is anti-symmetric if whenever both and hold, then must equal : . The relation “less than or equal to” () is anti-symmetric: if and , then . The relation “divides” on natural numbers is also anti-symmetric.

Key distinction: Asymmetric implies anti-symmetric AND irreflexive, but anti-symmetric does not imply asymmetric.

1.2.3 Transitivity

A relation on set is transitive if whenever is related to and is related to , then is also related to : .

Examples of transitive relations:

• “Less than” (<): if and , then
• “Equals” (=): if and , then
• “There is a path from city x to city y”: if there’s a path from x to y and from y to z, there’s a path from x to z

Examples of non-transitive relations:

• “x + y = 0”: if and , it doesn’t follow that
• “x is a friend of y”: friends of friends are not necessarily friends

1.2.4 Connexity

A relation on set is connex (also called total or complete) if for any two elements, at least one direction of the relationship holds: . The relation “less than or equal to” () on numbers is connex because for any two numbers, one is less than or equal to the other.

The relation “is a friend of” is not connex because two people might not be friends in either direction.

1.3 Representations of Binary Relations

Binary relations can be represented in multiple ways, each offering different insights.

1.3.1 Matrix Representation

For a relation on a finite set , we can represent as an matrix where:

This representation makes properties visually apparent:

• Reflexive: All 1s on the main diagonal
• Irreflexive: All 0s on the main diagonal
• Symmetric: Matrix equals its transpose ()
• Anti-symmetric: If and , then
• Connex: For , cannot have both and

1.3.2 Graph Representation

A relation can be visualized as a directed graph (digraph) where:

• Vertices (nodes) represent elements of the set
• Directed edges (arcs, arrows) represent the relation: an arrow from to means
• Loops (self-loops) at a vertex represent reflexive pairs

Graph properties:

• Reflexive: Loop at every vertex
• Irreflexive: No loops at any vertex
• Symmetric: For every edge from to , there’s an edge from to (bidirectional arrows)
• Asymmetric: Never two edges in opposite directions between distinct vertices
• Transitive: If there’s an edge from to and from to , there must be an edge from to
• Connex: Between any two distinct vertices, at least one directed edge exists

1.4 Counting Relations on Finite Sets

For a finite set with elements, we can count how many relations have specific properties.

1.4.1 Total Number of Relations

Any binary relation on is a subset of , which has elements (all possible pairs). Since a relation is any subset, the total number of binary relations is .

1.4.2 Reflexive Relations

For a reflexive relation, all diagonal elements must be in the relation (fixed as 1). The remaining pairs can be either included or excluded. Therefore, there are reflexive relations.

1.4.3 Irreflexive Relations

Similarly, for irreflexive relations, all diagonal elements must NOT be in the relation (fixed as 0), giving irreflexive relations.

1.4.4 Symmetric Relations

For a symmetric relation, if , then . We need to count pairs independently:

• Diagonal elements: choices (each can be 0 or 1)
• Off-diagonal elements: independent pairs (choosing one determines the other)

Total: symmetric relations.

1.4.5 Asymmetric Relations

For asymmetric relations, diagonal elements must all be 0 (irreflexive). For off-diagonal pairs with , we have 3 choices: include , include , or include neither. There are such independent pairs.

Total: asymmetric relations.

1.4.6 Anti-symmetric Relations

For anti-symmetric relations:

• Diagonal elements: choices (each can be 0 or 1)
• Off-diagonal pairs: For each pair with , we have 3 choices: include , include , or include neither (but not both)

Total: anti-symmetric relations.

1.4.7 Transitive Relations

Counting transitive relations is extremely difficult — no simple closed formula exists. The count grows much more slowly than because the transitivity constraint is very restrictive.

1.5 Special Types of Relations

1.5.1 Partial Order Relations

A strict (partial) order is a binary relation that is:

• Irreflexive:
• Asymmetric:
• Transitive:

Example: “Less than” (<) on numbers.

A non-strict (partial) order is a binary relation that is:

• Reflexive:
• Anti-symmetric:
• Transitive:

Example: “Less than or equal to” () on numbers.

Relationship: A non-strict order can be obtained from a strict order by adding equality: .

An example of a partial order that’s not immediately obvious: For vectors in , we can define if and only if for all . This is a partial order because some vectors are not comparable (e.g., and are incomparable).

1.5.2 Linear Order Relations

A linear order (also called total order) is a non-strict partial order that is also connex:

• Reflexive:
• Anti-symmetric:
• Transitive:
• Connex:

Example: “Less than or equal to” () on real numbers. The connexity property means any two elements are comparable.

For a set with elements, the number of linear orders is (n factorial). This is because a linear order corresponds to arranging the elements in a sequence, and there are permutations of elements.

1.5.3 Equivalence Relations

An equivalence relation is a binary relation that is:

• Reflexive:
• Symmetric:
• Transitive:

Common notations for equivalence relations: , , ,

Examples:

• Equality (=) on any set
• “Has the same cardinality as” for sets:
• “Has the same age as” for people (counting only years)
• “Is logically equivalent to” for logical formulas:

Equivalence Classes: An equivalence relation partitions the set into disjoint subsets called equivalence classes. An equivalence class is a maximal set of elements that are all equivalent to each other. For any element , its equivalence class is .

Main Property: Two equivalence classes are either identical or disjoint — they cannot partially overlap. This means an equivalence relation creates a partition of the set into non-overlapping groups.

1.6 Graph Theory Basics

1.6.1 Terminology

The field of graph theory has varied terminology across different texts and contexts. Frank Harary, a pioneer in graph theory, noted that “even the very word ‘graph’ has not been sacrosanct” and recommended that speakers clarify their terminology in advance.

A directed graph (digraph) is essentially equivalent to a binary relation. Common alternative terms:

Mathematical Term	Graph Theory Terms
Elements	Vertices, nodes, points
Relations	Edges, arcs, lines, links

1.6.2 Properties in Graph Language

All the relation properties we’ve discussed can be expressed in graph-theoretic terms:

• Reflexive: Loop at every vertex
• Irreflexive: No loops
• Symmetric: Bidirectional edges between all connected vertices
• Asymmetric: No bidirectional edges (all edges are one-way)
• Transitive: If there’s an edge and an edge , there must be an edge
• Connex: Between any two distinct vertices, at least one directed edge exists

---

2. Definitions

• Relation: Any set on sets .
• Binary Relation: A set relating elements of set to elements of set . When , it’s a binary relation on .
• Reflexive: A relation on where — every element is related to itself.
• Irreflexive (Anti-reflexive): A relation on where — no element is related to itself.
• Symmetric: A relation on where — if relates to , then relates to .
• Asymmetric: A relation on where — if relates to , then does not relate to .
• Anti-symmetric: A relation on where — if both and hold, then equals .
• Transitive: A relation on where — if relates to and relates to , then relates to .
• Connex (Total, Complete): A relation on where — for any two elements, at least one direction of relation holds.
• Strict Partial Order: A relation that is irreflexive, asymmetric, and transitive.
• Non-strict Partial Order: A relation that is reflexive, anti-symmetric, and transitive.
• Linear Order (Total Order): A relation that is reflexive, anti-symmetric, transitive, and connex.
• Equivalence Relation: A relation that is reflexive, symmetric, and transitive.
• Equivalence Class: For an equivalence relation on and element , the set of all elements equivalent to .
• Directed Graph (Digraph): A visual representation of a binary relation with vertices (elements) connected by directed edges (arrows).

---

3. Formulas

• Total Number of Binary Relations on Elements:
• Number of Reflexive Relations on Elements:
• Number of Irreflexive Relations on Elements:
• Number of Symmetric Relations on Elements:
• Number of Asymmetric Relations on Elements:
• Number of Anti-symmetric Relations on Elements:
• Number of Linear Orders on Elements:
• Asymmetric Relation Equivalence: A relation is asymmetric if and only if it is both anti-symmetric and irreflexive.
• Matrix Element Definition: For relation on , if , else .
• Non-strict from Strict Order:

---

4. Practice

4.1. Line Crossing Relation (Lab 8, Task 1a)

Consider the relation “line crosses line ” on the set of lines on a plane. Determine the properties of this relation.

Click to see the solution

1. Reflexive? Does a line cross itself?
   • Answer: No — a line doesn’t cross itself.
2. Irreflexive? Does no line cross itself?
   • Answer: Yes — no line crosses itself.
3. Symmetric? If line crosses line , does line cross line ?
   • Answer: Yes — crossing is mutual.
4. Asymmetric? If line crosses line , does line NOT cross line ?
   • Answer: No — crossing is symmetric, not asymmetric.
5. Anti-symmetric? If line crosses line and line crosses line , does ?
   • If two lines cross each other, they cross each other (symmetric), but they’re not the same line.
   • Answer: No — distinct lines can cross.
6. Transitive? If line crosses line and line crosses line , does line cross line ?
   • Counterexample: Three lines meeting at a point, where line 1 crosses line 2, line 2 crosses line 3, but lines 1 and 3 are parallel (don’t cross).
   • Answer: No — not transitive.
7. Connex? For any two lines, does one cross the other?
   • Counterexample: Parallel lines don’t cross.
   • Answer: No — parallel lines exist.

Answer: Irreflexive and symmetric only.

4.2. “Greater by 2” Relation (Lab 8, Task 1b)

Consider the relation “number is more than number by 2” on the set of natural numbers. Determine the properties of this relation.

Click to see the solution

The relation is:

1. Reflexive? Is for all ?
   • Answer: No — never true.
2. Irreflexive? Is for all ?
   • Answer: Yes — always true.
3. Symmetric? If , is ?
   • If , then
   • Answer: No — not symmetric.
4. Asymmetric? If , is ?
   • Yes, if , then , so
   • Answer: Yes — asymmetric.
5. Anti-symmetric? If and , does ?
   • The premise is impossible (would require ), so vacuously true
   • Answer: Yes — vacuously true.
6. Transitive? If and , is ?
   • From and , we get
   • Answer: No — not transitive.
7. Connex? For any two natural numbers and , is or ?
   • Counterexample: For , neither nor is true.
   • Answer: No — not connex.

Answer: Irreflexive, asymmetric, and anti-symmetric.

4.3. Divisibility Relation (Lab 8, Task 1c)

Consider the relation “number is divisible by number ” (denoted ) on the set of natural numbers. Determine the properties of this relation.

Click to see the solution

1. Reflexive? Is every number divisible by itself?
   • Answer: Yes — for all natural numbers .
2. Irreflexive? Is no number divisible by itself?
   • Answer: No — every number is divisible by itself.
3. Symmetric? If , is ?
   • Counterexample: but
   • Answer: No — not symmetric.
4. Asymmetric? If , is ?
   • Counterexample: (reflexive pairs violate asymmetry)
   • Answer: No — not asymmetric.
5. Anti-symmetric? If and , does ?
   • If and , then and for natural numbers .
   • This gives , so , which means , thus .
   • Answer: Yes — anti-symmetric.
6. Transitive? If and , is ?
   • If and , then , so
   • Answer: Yes — transitive.
7. Connex? For any two natural numbers and , is or ?
   • Counterexample: and
   • Answer: No — not connex.

Answer: Reflexive, anti-symmetric, and transitive (it’s a non-strict partial order).

4.4. Matrix Properties (2) (Lab 8, Task 2)

For each of the following matrices, determine the properties of the corresponding relation on set :

(Matrix 1)

(Matrix 2)

(Matrix 3)

(Matrix 4)

Click to see the solution

Matrix 1:

1. Reflexive? Diagonal: — Yes
2. Irreflexive? Has 1s on diagonal — No
3. Symmetric? Check if :
   • (different) — No
4. Asymmetric? Has reflexive pairs — No
5. Anti-symmetric? Check pairs with both directions = 1:
   • No such pairs exist for distinct elements — Yes
6. Transitive? Check all :
   • : need — No
7. Connex? Check all distinct pairs:
   • : ✓
   • : ✓
   • : ✗ — No

Answer for Matrix 1: Reflexive and anti-symmetric.

Matrix 2:

1. Reflexive? Diagonal: — No
2. Irreflexive? All diagonal elements are 0 — Yes
3. Symmetric? Check if :
   • ✓
   • ✓
   • ✓
   • ✓
   • ✓
   • ✓
   • Yes — symmetric
4. Asymmetric? Has bidirectional edges — No
5. Anti-symmetric? Has pairs with both directions = 1 for distinct elements — No
6. Transitive?
   • : need — No
7. Connex? No reflexive pairs, so not connex — No

Answer for Matrix 2: Irreflexive and symmetric.

Matrix 3:

1. Reflexive? Diagonal: — Yes
2. Irreflexive? — No
3. Symmetric? — No
4. Asymmetric? Has reflexive pairs — No
5. Anti-symmetric? No bidirectional pairs for distinct elements — Yes
6. Transitive?
   • Check : requires for transitivity
   • Row 2 = , so — No
7. Connex? : — No

Answer for Matrix 3: Reflexive and anti-symmetric.

Matrix 4:

1. Reflexive? Diagonal: — No
2. Irreflexive? — No
3. Symmetric? — No
4. Asymmetric? — No
5. Anti-symmetric? Check: : but — No
6. Transitive? Many violations — No
7. Connex? Element 2 and 4 not self-related — No

Answer for Matrix 4: None of the standard properties.

4.5. Graph Properties from Diagrams (Lab 8, Task 3)

For each of the nine directed graphs shown (with vertices {1, 2, 3}), determine which are reflexive, symmetric, and transitive.

Click to see the solution

We write R for reflexive, S for symmetric, and T for transitive.

1. Graph 1
   • Every vertex has a loop R.
     
   • For each edge between distinct vertices (1–2 and 2–3) the reverse edge is also present S.
     
   • There is a path but no edge , so it is not T.
     
   • Conclusion: R, S, not T.
2. Graph 2
   • Vertex 3 has no loop not R.
     
   • The only non‑loop edges are between 2 and 3 in both directions, so every edge has its reverse S.
     
   • From and we would need for transitivity, which is missing not T.
     
   • Conclusion: S, not R, not T.
3. Graph 3
   • Every vertex has a loop R.
     
   • Around the triangle the edges go in one direction only, so some edges do not have their reverses not S.
     
   • For example, and hold but there is no not T.
     
   • Conclusion: R, not S, not T.
4. Graph 4
   • Every vertex has a loop R.
     
   • Between 1 and 2 we have edges both ways, and there are no edges between and 3, so every non‑loop edge has its reverse S.
     
   • This is exactly the equivalence relation with classes and , hence T.
     
   • Conclusion: R, S, T.
5. Graph 5
   • Vertex 3 has no loop not R.
     
   • Between 1 and 2 we have edges in both directions, and there are no other non‑loop edges S.
     
   • Any composable pair of edges starts and ends within , and those compositions are present, so the relation is T.
     
   • Conclusion: S, T, not R.
6. Graph 6
   • Every vertex has a loop R.
     
   • Between each pair of distinct vertices we have edges in both directions, so every edge has its reverse S.
     
   • This is the universal relation on (all ordered pairs), which is clearly T.
     
   • Conclusion: R, S, T.
7. Graph 7
   • Only loops, one at each vertex, so every vertex is related to itself R.
     
   • Every edge is of the form , whose reverse is itself, so S.
     
   • Any composable pair , yields , which is present, so T.
     
   • Conclusion: R, S, T.
8. Graph 8
   • Every vertex has a loop R.
     
   • For each edge between distinct vertices, the reverse edge is also present S.
     
   • Whenever there is a path , the direct edge is also in the diagram, so the relation is T.
     
   • Conclusion: R, S, T.
9. Graph 9
   • Every vertex has a loop R.
     
   • There are edges and without the reverse edges and , so not S.
     
   • Any composable non‑loop pair starts at 1 and ends at 1, 2, or 3; all necessary compositions already appear (e.g., from and we still get ), so the relation is T.
     
   • Conclusion: R, T, not S.

4.6. “Father of” Relation Properties (Tutorial 8, Task 1)

Let be the set of all humans, and define is “a father of” . Determine which properties this relation has.

Click to see the solution

Key Concept: Check each property definition against the real-world meaning of the relation.

1. Reflexive?
   • This would mean every person is their own father.
   • Answer: No — this is clearly false.
2. Irreflexive?
   • This means no person is their own father.
   • Answer: Yes — this is true.
3. Symmetric?
   • This would mean if is a father of , then is a father of .
   • Answer: No — children are not fathers of their fathers.
4. Asymmetric?
   • This means if is a father of , then is not a father of .
   • Answer: Yes — this is true (the relation only goes in one direction).
5. Anti-symmetric?
   • Since the premise is always false (you can’t have both is father of AND is father of ), the implication is vacuously true.
   • Answer: Yes — vacuously true.
6. Transitive?
   • This would mean if is a father of , and is a father of , then is a father of .
   • But this describes grandfather, not father.
   • Answer: No — grandfathers are not fathers.
7. Connex?
   • This would mean for any two people, one is a father of the other.
   • Answer: No — most pairs of people have no father-child relationship.

Answer: Irreflexive, asymmetric, and anti-symmetric.

4.7. Matrix Relation Properties (1) (Tutorial 8, Task 2)

Consider a relation on set represented by the matrix:

Determine all properties of this relation.

Click to see the solution

1. Reflexive? Check the main diagonal:
   • Diagonal elements: , ,
   • Answer: No — not all diagonal elements are 1.
2. Irreflexive? Check if all diagonal elements are 0.
   • Diagonal has
   • Answer: No — at least one diagonal element is 1.
3. Symmetric? Check if for all .
   • but (not equal)
   • Answer: No — matrix is not symmetric.
4. Asymmetric? Check if whenever , we have .
   • and (both are 1, violates asymmetric for )
   • Answer: No — has a reflexive pair.
5. Anti-symmetric? Check if and implies .
   • For all off-diagonal pairs where , we check :
   • ✓
   • ✓
   • ✓
   • Answer: Yes — no two distinct elements have bidirectional relation.
6. Transitive? Check if and implies .
   • : need ✓ (it is)
   • Check all other combinations…
   • Answer: Yes — all transitivity conditions are satisfied.
7. Connex? Check if for all , we have .
   • The definition requires , which includes the case .
   • For , this means .
   • Checking diagonal elements: ✓, ✗, ✗
   • Since elements 2 and 3 don’t relate to themselves, the relation is not connex.
   • Answer: No — not all elements satisfy .

Answer: Yes for anti-symmetric and transitive; No for all others.

4.8. Graph Relation Properties (Tutorial 8, Task 3)

Consider the directed graph with vertices and edges: (loop), , , . Determine the properties of this relation.

Click to see the solution

1. Reflexive? Check if every vertex has a loop.
   • has a loop ✓
   • has no loop ✗
   • has no loop ✗
   • Answer: No
2. Irreflexive? Check if no vertex has a loop.
   • has a loop
   • Answer: No
3. Symmetric? Check if every edge has a reverse edge.
   • Edge exists, but does not exist
   • Answer: No
4. Asymmetric? Check if no two distinct vertices have edges in both directions, AND no loops.
   • There’s a loop at , which violates asymmetry
   • Answer: No
5. Anti-symmetric? Check if there are no bidirectional edges between distinct vertices.
   • No two distinct vertices have edges in both directions
   • Answer: Yes
6. Transitive? Check if and implies .
   • and : need ✓ (present)
   • and : need ✓ (present)
   • and : need ✓ (present)
   • and : already checked
   • All transitivity conditions satisfied
   • Answer: Yes
7. Connex? Check if between any two distinct vertices, at least one directed edge exists. Also need all elements to be self-related.
   • Elements and don’t have loops, so they’re not related to themselves
   • Answer: No

Answer: Anti-symmetric and transitive only.

4.9. Total Number of Relations (Tutorial 8, Task 4)

What is the number of all binary relations on a set with elements?

Click to see the solution

Key Concept: A binary relation on a set is any subset of .

1. Count total pairs: For a set with elements, has ordered pairs: .
2. Count subsets: Any binary relation is a subset of . A set with elements has subsets (each element can be either included or excluded independently).

Answer:

4.10. Number of Reflexive Relations (Tutorial 8, Task 5)

What is the number of all reflexive relations on a set with elements?

Click to see the solution

Key Concept: For reflexive relations, all diagonal elements are fixed (must be included), but other elements are free to choose.

1. Fixed elements: All diagonal pairs must be in the relation (reflexivity requirement).
2. Free elements: The remaining non-diagonal pairs can either be included or excluded.
3. Count possibilities: For the free pairs, we have ways to choose subsets.

Answer:

4.11. Number of Irreflexive Relations (Tutorial 8, Task 6)

What is the number of all irreflexive relations on a set with elements?

Click to see the solution

Key Concept: For irreflexive relations, all diagonal elements are fixed (must be excluded), reasoning is similar to reflexive case.

1. Fixed elements: All diagonal pairs must NOT be in the relation (irreflexivity requirement).
2. Free elements: The remaining non-diagonal pairs can either be included or excluded.
3. Count possibilities: ways.

Answer:

4.12. Number of Symmetric Relations (Tutorial 8, Task 7)

What is the number of all symmetric relations on a set with elements?

Click to see the solution

Key Concept: For symmetric relations, if we include , we must include . So pairs come in linked groups (except diagonal).

1. Diagonal elements: Each of the diagonal pairs can independently be included or excluded: choices.
2. Off-diagonal elements: For , pairs and must be chosen together. There are such independent pairs (counting each unordered pair once).
3. Total count:

Answer:

4.13. Number of Asymmetric Relations (Tutorial 8, Task 8)

What is the number of all asymmetric relations on a set with elements?

Click to see the solution

Key Concept: Asymmetric relations are both anti-symmetric and irreflexive. For each unordered pair of distinct elements, we have 3 choices.

1. Diagonal elements: All must be excluded (irreflexive), so no choice: way.
2. Off-diagonal pairs: For distinct elements and (with ), we have 3 possibilities:
   • Include but not
   • Include but not
   • Include neither nor
   There are such unordered pairs.
3. Total count:

Answer:

4.14. Number of Anti-symmetric Relations (Tutorial 8, Task 9)

What is the number of all anti-symmetric relations on a set with elements?

Click to see the solution

Key Concept: Anti-symmetric means we cannot have both and for distinct . Diagonal elements are free.

1. Diagonal elements: Each of the diagonal pairs can independently be included or excluded: choices.
2. Off-diagonal pairs: For each unordered pair of distinct elements with , we have 3 possibilities:
   • Include but not
   • Include but not
   • Include neither
   There are such unordered pairs.
3. Total count:

Answer:

4.15. Number of Transitive Relations (Tutorial 8, Task 10)

What is the number of all transitive relations on a set with elements?

Click to see the solution

Key Concept: There is no simple closed formula for counting transitive relations. The count depends heavily on and grows much slower than .

The source material provides a table of values:

Elements ()	Any Relations	Transitive	Reflexive	Symmetric
1	2	2	1	2
2	16	13	4	8
3	512	171	64	64
4	65536	3994	4096	1024
		???

Answer: No simple formula exists. For small : 2 (n=1), 13 (n=2), 171 (n=3), 3994 (n=4).

4.16. Number of Linear Orders (Tutorial 8, Task 11)

What is the number of all linear orders on a set with elements?

Click to see the solution

Key Concept: A linear order on a finite set corresponds to a complete ordering (permutation) of the elements.

A linear order must be reflexive, anti-symmetric, transitive, and connex. The connexity property means every pair of distinct elements must be comparable — one must be “less than or equal to” the other.

For elements, a linear order is equivalent to arranging them in a sequence: . The number of such sequences is the number of permutations of elements.

Answer: